package _binary_tree

import common.TreeNode
import org.junit.Assert
import org.junit.Test
import java.util.*
import kotlin.collections.ArrayList

/**


https://leetcode.cn/problems/invert-binary-tree/description/
https://programmercarl.com/0226.%E7%BF%BB%E8%BD%AC%E4%BA%8C%E5%8F%89%E6%A0%91.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE

 * 题型：二叉树的任何一种遍历方式
 *
 * 226. 翻转二叉树
给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
示例 1：
输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]

示例 2：
输入：root = [2,1,3]
输出：[2,3,1]
示例 3：

输入：root = []
输出：[]
 */
class leetcode_226 {
    @Test
    fun test_1() {
        // 4,2,7,1,3,6,9
        val root = TreeNode(4)
        val n2 = TreeNode(2)
        val n7 = TreeNode(7)
        val n1 = TreeNode(1)
        val n3 = TreeNode(3)
        val n6 = TreeNode(6)
        val n9 = TreeNode(9)
        root.left = n2
        root.right = n7
        n2.left = n1
        n2.right = n3
        n7.left = n6
        n7.right = n9

        val actual = print(invertTree(root))
        val expect = intArrayOf(4, 7, 2, 9, 6, 3, 1)
        Assert.assertEquals(expect.contentToString(), actual.contentToString())
    }

    @Test
    fun test_2() {
        val root = TreeNode(2)
        val n1 = TreeNode(1)
        val n3 = TreeNode(3)
        root.left = n1
        root.right = n3
        val actual = print(invertTree(root))
        val expect = intArrayOf(2, 3, 1)
        Assert.assertEquals(expect.contentToString(), actual.contentToString())
    }

    @Test
    fun test_3() {
        val actual = print(invertTree(null))
        val expect = intArrayOf()
        Assert.assertEquals(expect.contentToString(), actual.contentToString())
    }

    private fun print(root: TreeNode?): IntArray {
        if (root == null) {
            return intArrayOf()
        }
        val list: ArrayList<Int> = ArrayList<Int>()
        val queue: LinkedList<TreeNode> = LinkedList<TreeNode>()
        queue.offer(root)
        while (!queue.isEmpty()) {
            val size = queue.size
            for (i in 1..size) {
                val node = queue.poll()
                list.add(node.`val`)
                node.left?.let {
                    queue.offer(it)
                }
                node.right?.let {
                    queue.offer(it)
                }
            }
        }
        return list.toIntArray()
    }

    private fun invertTree(root: TreeNode?): TreeNode? {
        // 题目：左右孩子的指针交换，不是数值交换
        // return invertTree1(root)
        // return invertTree2(root)
        // return invertTree3(root)
        // return invertTree4(root)
        // return invertTree5(root)
        return invertTree6(root)
        return invertTree7(root)
    }

    // 深度遍历 - 前序 - 递归
    private fun invertTree1(node: TreeNode?): TreeNode? {
        // T - N
        // S - H
        if (null == node) {
            return node
        }
        // 前序遍历：中左右
        val temp: TreeNode? = node.right
        node.right = node.left
        node.left = temp

        invertTree1(node.left)
        invertTree1(node.right)
        return node
    }

    // 深度遍历 - 后序 - 递归
    private fun invertTree2(node: TreeNode?): TreeNode? {
        // T - N
        // S - H
        if (null == node) {
            return null
        }
        invertTree2(node.left)
        invertTree2(node.right)

        val temp: TreeNode? = node.right
        node.right = node.left
        node.left = temp
        return node
    }


    // 深度遍历 - 中序 - 递归
    private fun invertTree3(node: TreeNode?): TreeNode? {
        // T - N
        // S - H
        if (null == node) {
            return null
        }
        invertTree3(node.left)

        val temp: TreeNode? = node.right
        node.right = node.left
        node.left = temp

        invertTree3(node.left)
        return node
    }

    // 深度遍历 - 前序 - 栈迭代:（统一写法）
    private fun invertTree4(node: TreeNode?): TreeNode? {
        if (null == node) {
            return null
        }

        val stack: LinkedList<TreeNode> = LinkedList<TreeNode>()
        stack.push(node)

        while (!stack.isEmpty()) {
            val node = stack.pop()
            if (null != node.right) {
                stack.push(node.right)
            }
            if (null != node.left) {
                stack.push(node.left)
            }
            val temp: TreeNode? = node.right
            node.right = node.left
            node.left = temp
        }
        return node
    }

    // 深度遍历 - 中序 - 栈迭代:（统一写法）
    private fun invertTree5(node: TreeNode?): TreeNode? {
        if (null == node) {
            return null
        }

        val stack: LinkedList<TreeNode> = LinkedList<TreeNode>()
        stack.push(node)

        while (!stack.isEmpty()) {
            val node = stack.pop()
            if (null != node.right) {
                stack.push(node.right)
            }
            val temp: TreeNode? = node.right
            node.right = node.left
            node.left = temp

            if (null != node.right) {
                stack.push(node.right)
            }
        }
        return node
    }

    // 深度遍历 - 后序 - 栈迭代（统一写法）
    private fun invertTree6(node: TreeNode?): TreeNode? {
        if (null == node) {
            return null
        }

        val stack: LinkedList<TreeNode> = LinkedList<TreeNode>()
        stack.push(node)

        while (!stack.isEmpty()) {
            val node = stack.pop()

            val temp: TreeNode? = node.right
            node.right = node.left
            node.left = temp


            if (null != node.right) {
                stack.push(node.right)
            }

            if (null != node.left) {
                stack.push(node.left)
            }
        }
        return node
    }

    // 广度遍历
    private fun invertTree7(node: TreeNode?): TreeNode? {
        if (null == node) {
            return null
        }

        val queue: LinkedList<TreeNode> = LinkedList<TreeNode>()
        queue.offer(node)

        while (!queue.isEmpty()) {
            var size = queue.size
            while (size-- > 0) {
                val node = queue.poll()

                val temp: TreeNode? = node.right
                node.right = node.left
                node.left = temp

                node.left?.let { queue.offer(it) }
                node.right?.let { queue.offer(it) }
            }
        }
        return node
    }
}